package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/">I.数组中只出现一次的两个数字</a>
 *
 * <p>一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。</p>
 * <p>数据范围：数组长度2≤n≤1000，数组中每个数的大小0< val ≤1000000</p>
 * <p>要求：空间复杂度O(1)，时间复杂度O(n)</p>
 *
 * @author c2b
 * @since 2023/3/8 13:50
 */
public class JzOffer0056SingleNumber_I {

    /**
     * 位运算
     * <p>
     * step 1：遍历整个数组，将每个元素逐个异或运算，得到a^b<br>
     * step 2：我们可以考虑位运算的性质，找到二进制中第一个不相同的位，将所有数组划分成两组。<br>
     * step 3：遍历数组对分开的数组单独作异或连算。<br>
     * step 4：最后整理次序输出。<br>
     * </p>
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] singleNumber(int[] array) {
        // write code here
        // 两个只出现一次的数字亦或(^)的结果
        int temp = 0;
        for (int i : array) {
            temp ^= i;
        }
        // 因为两个数字不相同，二进制必定会有一位不同的。我们就以这一位是否为1来划分上述的两个数组，相同的数字自然会被划分到另一边，而a与b也会刚好被分开。
        // 找出结果中最低位的1首次出现的位置
        int mask = 1;
        while ((temp & mask) == 0) {
            mask = mask << 1;
        }
        // 根据最低位的1出现的位置，对所有数字进行分组，一组为该位置为1的，一组为该位置不为1的
        int resA = 0;
        int resB = 0;
        for (int num : array) {
            if ((num & mask) == 0) {
                // 该最低位不相等的分组
                resA ^= num;
            } else {
                // 该最低位相等的分组
                resB ^= num;
            }
        }
        // 输出时按非降序排列
        return new int[]{resA, resB};
    }

    public static void main(String[] args) {
        JzOffer0056SingleNumber_I jzOffer0056FindNumsAppearOnce_ = new JzOffer0056SingleNumber_I();
        int[] ints = jzOffer0056FindNumsAppearOnce_.singleNumber(new int[]{1, 4, 1, 6});
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
